1. Field of the Invention
The present invention relates to high speed packet switching in general, and to space-division switching of fixed length data packets in particular. More particularly still, it relates to asynchronous transfer mode (ATM) packet switching by means of input-buffered N.times.N switching or cross-point matrices.
2. Prior Art of the Invention
A useful introduction briefly summarizing the state of the art is given by J. Y. Hui in a paper published Mar. 1989 in IEEE Network titled "Network, Transport, and Switching Integration for Broadband Communications" under the subheading "Packet Switching for ATM Networks" at page 49. This part of the paper is quoted in full below:
"We now consider switching mechanisms for interconnection of ATM links. In particular, we shall focus on the predominant mode of ATM, namely, the format using fixed length packets or cells. PA0 The TMS, used for switching STM links, can also be reconfigured per packet time for connecting ATM links. The same problem of output contention for the TMS arises. As we mentioned before, circuit switching connecting STM links utilizes TSI at both the inputs and outputs to solve this output contention and mismatch problem. However, this is impossible for ATM networks for two reasons. PA0 First, ATM is inherently an FCFS network without a frame reference. Hence, a packet on an input ATM link would have to wait until the output is available. Consequently, an FCFS waiting room via buffering, instead of buffering for TSI, is necessary at the inputs. PA0 Second and more important, the destination addresses of packets on an ATM link may not have the periodic structure inherent in an STM network, for which each slot in a frame is dedicated to the communication between two terminals. The periodic structure for STM implies that the cross-point setting of the TMS reconfigures periodically per frame. Therefore, the cross-point settings per frame can be precomputed and stored for controlling the TMS. This computation can become quite complicated when the TMS itself is a multi-stage network. So far, efforts for producing a fast parallel control algorithm for the TST network have failed to give a satisfactory control method for packet switching, for which the TMS cross-point setting has to be recomputed once per packet time since the input-output connection pattern changes every slot. PA0 Two major switching methodologies are currently known for interconnecting large numbers of ATM links. The first approach alleviates output contention, or contention anywhere in a multi-stage connection network, by extensively using FCFS buffering at the internal links of the switching network. The interconnection network used is often a variation of the banyan network [14]. Therefore, contention is localized to switch nodes with buffering to hold contending packets, PA0 The second approach avoids the use of internal buffering but employs sorting as a switching mechanism for computing cross-point setting and resolving output contention. The interconnection network used is a Batcher sorting network placed before a banyan-type network. This Batcher-banyan approach [15] [16]is more suitable for optical implementation than the buffered banyan approach because less buffering is necessary." PA0 "Using Markov chain models, queueing theory, and simulation, we have presented a thorough comparison of input versus output queueing on an N.times.N nonblocking space-division packet switch. What the present exercise has done, for a particular solvable example, is to quantify the intuition that better performance results with output queueing than with input queueing." PA0 "Cell switching is realized by transmitting cells through the OSM after setting the OSM connections according to the destination port number obtained from the VCI in the cell header. Cells in the input buffers are processed on a first-in first-out basis. Destination port numbers of the cells are analyzed by the cell output controller (OUT CONT) and transferred to the cell switch controller (SW CONT). The cell switch controller analyzes cell transfer requirements and determines cells to be transferred. When plural cells are destined to the same output port, only one cell is selected. Arbitration results are sent back to the cell output controllers and, OSM connections are arranged simultaneously. The cell output controllers which obtain permission for cell transfer, send cells to the OSM and the cells are then transferred to the destined output ports."
In an earlier paper by Mark J. Karol et al published in the IEEE Transactions On Communications, Vol. COM-35, No. 12, Dec. 1987, p. 1347, entitled "Input Versus Output Queueing on a Space-Division Packet Switch", the authors conclude as follows:
The closest prior art known is disclosed in a paper by H. Inoue et al, titled "InP Based 4.times.4 Optical Switch Module and Its Application to ATM Switching", published in the Proceedings of the OSA Topical Meeting of Photonic Switching 1989 at pages 115-117 (paper FA4). Even though the paper is not directly concerned with the subject matter of the present invention. FIG. 8 therein, showing a "Switching stage", has a 4.times.4 space-division switching module (OSM) having input buffer memory (Input BFM).
The associated description, under the subheading "(2) Switching stage", is as follows:
In the switching stage of Inoue et al, only one input buffer per input port of the switching matrix is used. For a switch with only four input ports, the use of a single FIFO (first-in-first-out) buffer would not result in unacceptable blocking, given favourable traffic statistics.
Other prior art includes the well-known Batcher-Banyan architecture, wherein input buffers precede a Batcher sorting network which is followed by contention detectors and a Banyan routing network. In such a network only packet or cell headers are launched from the input buffers into the sorting network at the output of which packets destined for the same output appear on adjacent ports. The contention detectors are a vertical slice of N-1 comparators. They detect identical destinations and report backwards through the still open two-way paths of the Batcher sorter to the input buffers. The contention detectors select one packet from each set having identical destination for a subsequent launch through the Banyan routing network. The basic unit of a Batcher-Banyan network is a 2-by-2 sorting and routing unit.
The two-phase (two launches) operation is necessary because it is not sufficient to present the routing network with just an ordered set of headers, wherein duplicates are identified by a "NOGO". Rather, the "GO" headers must also appear on contiguous ports with all the "NOGO" headers arranged to one side. By relaunching the packets in the second phase with all "NOGO" packets given a numerical header value of either 0 to N+1 (in an N.times.N matrix), the sorting network will cause all "NOGO" packets to aggregate at one end of the cross section of ports. The same objective could be achieved in a single phase by adding a second sorting network between contention detectors and routing network. However, it is likely that the disadvantage of delay and logic overhead of double launching is less than that of adding a third network. And in any event, notification of "NOGO" packets still have to be fedback to the input buffers to allow retries on subsequent switching cycles.